#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
// 不同的子序列：https://leetcode.cn/problems/distinct-subsequences/description/
using namespace std;
class Solution {
public:
    int numDistinct(string s, string t) {
        int n=s.size();
        int m=t.size();
        s=" "+s;
        t=" "+t;
        vector<vector<double>> dp(m+1,vector<double>(n+1));
        for(int i=0;i<=n;i++) dp[0][i]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
                dp[i][j]=((s[j]==t[i])?dp[i-1][j-1]:0)+dp[i][j-1];
        }
        return dp[m][n];
    }
};